from typing import List

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        self.n = len(s)
        self.result = []
        self.path = []
        self.s = s
        self.wordHash = {}
        self.backtracking(0)
        return self.result
    
    def backtracking(self,start_index):
        if start_index==self.n:
            self.result.append(self.path[:])
            return
        for i in range(start_index,self.n):
            if not self.isValid(self.s[start_index:i+1]): continue
            self.path.append(self.s[start_index:i+1])
            self.backtracking(i+1)
            self.path.pop()

    def isValid(self,strs):
        if strs in self.wordHash:
            return self.wordHash[strs]
        left = 0
        right = len(strs)-1
        while left <= right:
            if strs[left] != strs[right]:
                self.wordHash[strs] = False
                return False
            left += 1
            right -= 1
        self.wordHash[strs] = True
        return True

if __name__ == "__main__":
    s = Solution()
    r = s.partition("aan")
    print(r)